package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月13日
*时间：上午11:37:57
*/
public class Q552ii {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] rs = new int[k];
        int l1 = 0;
        int l2 = 0;
        for (int i = 0; i < k; i++) {
            int right1 = nums1.length + nums2.length - l2 - (k - i) + 1;
            right1 = nums1.length > right1 ? right1 : nums1.length;
            int right2 = nums2.length + nums1.length - l1 - (k - i) + 1;
            right2 = nums2.length > right2 ? right2 : nums2.length;
            Point a = findMax(nums1, l1, right1);
            Point b = findMax(nums2, l2, right2);
            if (a.value > b.value) {
                rs[i] = a.value;
                l1 = a.point + 1;
            } else if (b.value > a.value) {
                rs[i] = b.value;
                l2 = b.point + 1;
            } else {
                rs[i] = a.value;
                if (chooseA(nums1, nums2, a, b)) {
                    l1 = a.point + 1;
                } else {
                    l2 = b.point + 1;
                }
            }
        }
        return rs;
    }

    /**
     * 这个判断不正确，
     * 不应该判断下一个连续的数
     * 要判断下一个可以取到的最大数
     * 参见Q552的递归
     * */
    private boolean chooseA(int[] nums1, int[] nums2, Point a, Point b) {
        int l1 = a.point;
        int l2 = b.point;
        while (l1 < nums1.length && l2 < nums2.length && nums1[l1] == nums2[l2]) {
            l1++;
            l2++;
        }
        if (l1 == nums1.length) {
            if (l2 == nums2.length) {
                return true;
            } else {
                return nums1[a.point] >= nums2[l2];
            }
        } else {
            if (l2 == nums2.length) {
                return nums1[a.point] <= nums1[l1];
            } else {
                return nums1[l1] >= nums2[l2];
            }
        }
    }

    private Point findMax(int[] num, int left, int right) {
        int point = -1;
        int max = -1;
        for (int i = left; i < right; i++) {
            if (num[i] > max) {
                point = i;
                max = num[i];
            }
        }
        return new Point(point, max);
    }

    class Point {
        public Point(int point, int value) {
            this.value = value;
            this.point = point;
        }

        int point;
        int value;
    }

    @Test
    public void TestA() {
        // [5,0,2,1,0,1,0,3,9,1,2,8,0,9,8,1,4,7,3], [7,6,7,1,0,1,0,5,6,0,5,0], 31
        int[] a = { 1, 5, 8, 1, 4, 0, 8, 5, 0, 7, 0, 5, 7, 6, 0, 5, 5, 2, 4, 3, 6, 4, 6, 6, 3, 8, 1, 1, 3, 1, 3, 5, 4, 3, 9, 5, 0, 3, 8, 1, 4, 9, 8, 8, 3, 4,
                6, 2, 5, 4, 1, 1, 4, 6, 5, 2, 3, 6, 3, 5, 4, 3, 0, 7, 2, 5, 1, 5, 3, 3, 8, 2, 2, 7, 6, 7, 5, 9, 1, 2 };
        int[] b = { 7, 8, 5, 8, 0, 1, 1, 6, 1, 7, 6, 9, 6, 6, 0, 8, 5, 8, 6, 3, 4, 0, 4, 6, 7, 8, 7, 7, 7, 5, 7, 2, 5, 2, 1, 9, 5, 9, 3, 7, 3, 9, 9, 3, 1, 4,
                3, 3, 9, 7, 1, 4, 4, 1, 4, 0, 2, 3, 1, 3, 2, 0, 2, 4, 0, 9, 2, 0, 1, 3, 9, 1, 2, 2, 6, 6, 9, 3, 6, 0 };
        int k = 80;
        int[] rs = maxNumber(a, b, k);
        for (int s : rs) {
            System.out.print(s + ",");
        }
    }
}
